\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{课后作业4.37}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle


\section{问题描述}
编写一个函数以二叉查找树 $T$ 和两个有序的关键字 $k_1$ 和 $ k_2$ ( $k_1 \le k_2$ ) 作为输入, 打印书中所有满足 $k_1 \le Key(x) \le k_2$ 的元素 $x$. 除去可以排序外, 不对关键字的类型做任何假设.所写的程序应该以平均时间 $O ( K + \log N)$ 运行, 其中 $K$ 是所打印的关键字的个数.确定你的算法的运行时间界.


\section{设计思路}
可以将题目中的Binary Search Tree 直接认为就是AVL Tree, 直接使用课本中 \verb|AvlTree.h| 文件的代码.自主完成函数实现查找并按值的顺序打印功能.

为节约运行时间采用递归算法,可分为以下几种情况处理: $k_1 \le x \le k_2$ 时, 中序遍历其余子树保证按值大小顺序输出; $k_2 < x$ 时, 只需遍历该节点左子树; $x < k_1$ 时,只需遍历该节点右子树.

\section{理论分析}
分析遍历调用 \verb|keyprint| 函数的节点,可分为两类: 第一类为遍历并进行打印的节点,即符合条件的节点, 共有 $K$ 个, 设运行时间为 $t(K)$ ; 第二类为遍历但不打印的节点,即需要对其单侧子树继续遍历, 下分析说明同一深度至多有两个这样的节点, 从而至多有 $2 \log N$ 个第二类节点.

若同一深度存在三个及以上第二类节点,取其中最左边的节点, 中间任意一个节点, 和最右边的节点 $n_1$, $n_2$, $n_3$. 可知 $n_1$, $n_2$ 存在共同父节点, 设距离该层最近的共同父节点为 $p_1$, 易知 $p$ 为第一类节点, $n_1$, $n_2$ 分别来自 $p_1$ 的左子树和右子树, 可得 $k_1 <$ \verb|$p_1$ -> data| $<$ \verb|$n_2$ -> data|.同理,考虑距离该层最近的 $n_2$, $n_3$ 的共同父节点 $p_2$, $n_2$, $n_3$ 分别来自 $p_2$ 的左子树和右子树, 可得 $k_2 >$ \verb|$p_2$ -> data| $>$ \verb|$n_2$ -> data|.由此可知, $k_1 <$ \verb|$n_2$ -> data| $< k_2$, 即$n_2$为第一类节点,矛盾.

综上可知,该程序对应的时间复杂度为 $O(t_1 * 2 \log N + t_2 * K)$, 即为 $O( \log N + K)$. 

\section{数值结果分析}
令 NUMS = 10, 分别运行 \verb|t.keyprint( 2, 8)|, \verb|t.keyprint( 11, 12)|, 输出结果如下图所示,可知函数可满足功能要求,且对于超出查找范围的关键字能正确处理,没有内容输出.
\begin{figure}[htpb]
	\center{\includegraphics{figure1.png}}
\end{figure}

令 NUMS = 10, 100, 1000, 10000, 100000, 1000000, TESTN = 10, 输出程序的平均运行时间, 可知算法满足理论分析.
\begin{center}
\begin{tabular}{l c c c c c c}
	NUMS & 10 & 100 & 1000 & 10000 & 100000 & 1000000\\
	1 & 0.0004 & 0.0011 & 0.0046 & 0.0478 & 0.6743 & 8.7605\\
	2 & 0.0006 & 0.0009 & 0.005 & 0.0432 & 0.5798 & 9.429\\
	3 & 0.001 & 0.0012 & 0.0068 & 0.0529 & 0.7406 & 7.9561\\
	4 & 0.0006 & 0.0009 & 0.0049 & 0.0441 & 0.7453 & 7.5364\\
	5 & 0.0012 & 0.0011 & 0.0063 & 0.0262 & 0.6935 & 6.2784\\
	6 & 0.0007 & 0.001 & 0.0057 & 0.054 & 0.5647 & 6.1383\\
	7 & 0.0008 & 0.0012 & 0.0064 & 0.0666 & 0.7732 & 7.1926\\
	8 & 0.0006 & 0.0012 & 0.0049 & 0.0329 & 0.7421 & 7.1436\\
	9 & 0.0003 & 0.0014 & 0.0049 & 0.043 & 0.5608 & 8.9647\\
	10 & 0.001 & 0.0013 & 0.0042 & 0.048 & 0.6222 & 6.2373\\
\end{tabular}
\end{center}

检查内存泄漏结果如下,可知没有发生内存泄漏.
\begin{verbatim}
==2747== Memcheck, a memory error detector
==2747== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2747== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2747== Command: ./main
==2747==
n = 10:0.4187ms
n = 100:0.0611ms
n = 1000:0.4321ms
n = 10000:3.4234ms
n = 100000:52.8964ms
n = 1000000:427.831ms
==2747== 
==2747== HEAP SUMMARY:
==2747==     in use at exit: 0 bytes in 0 blocks
==2747==   total heap usage: 1,000,002 allocs, 1,000,002 frees, 32,073,728 bytes allocated
==2747== 
==2747== All heap blocks were freed -- no leaks are possible
==2747== 
==2747== For counts of detected and suppressed errors, rerun with: -v
==2747== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

\end{verbatim}


\end{document}
